/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
/* 
为了在二维网格中查找单词，可以使用回溯法（深度优先搜索）遍历每个可能的路径。
从每个单元格出发，递归检查相邻单元格是否匹配单词的下一个字符，同时标记已访问的单元格避免重复使用。

方法思路
遍历网格：对于每个单元格，检查是否与单词的第一个字符匹配。
深度优先搜索（DFS）：从匹配的单元格出发，递归检查四个方向的相邻单元格是否匹配单词的后续字符。
标记与回溯：在递归过程中标记当前单元格为已访问，回溯时恢复状态，确保每个单元格仅被使用一次。
剪枝优化：若当前路径无法匹配单词，立即终止搜索以减少不必要的计算。
*/
var exist = function (board, word) {
  const m = board.length;
  const n = board[0].length;
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // 上、下、左、右

  // 检查从坐标(row, col)开始是否能匹配单词
  const dfs = (row, col, index) => {
    // 若越界、字符不匹配或已访问，返回false
    if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] !== word[index]) {
      return false;
    }

    // 若已匹配到单词最后一个字符，返回true
    if (index === word.length - 1) {
      return true;
    }

    // 标记当前单元格为已访问（用空字符覆盖）
    const originalChar = board[row][col];
    board[row][col] = '';

    // 递归检查四个方向
    for (const [dx, dy] of directions) {
      if (dfs(row + dx, col + dy, index + 1)) {
        return true;
      }
    }

    // 回溯，恢复单元格状态
    board[row][col] = originalChar;
    return false;
  };

  // 遍历每个单元格，尝试作为起点
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (dfs(i, j, 0)) {
        return true;
      }
    }
  }

  return false;
};